#include <iostream>
#include <algorithm>

using namespace std;

const int N = 60;

int n;
int ans;
int a[N], up[N], down[N];

void dfs(int u, int su, int sd) { 
    // u 为当前序列点的序号， su为当前上升子序列的个数， sd为当前上升子序列的个数
    if (su + sd >= ans) return ; // 如果两个子序列的个数之和大于等于整个序列长度就退出搜索
    if (u == n) { // 如果遍历完整个序列的话
        ans = min(ans, su + sd); // 就将答案更新为当前存的答案和su+sd的最小值
        return ; // 然后退出搜索
    }
    // 情况1：用上升子序列设置系统
    int k = 0; // 初始化当前搜索上升子序列序号为0
    while (k < su && up[k] >= a[u]) k ++ ; 
/* 如果当前搜索的点小于等于当前搜索的上升子序列末尾值且当前搜索的序列序号小于当前有的上升子序列的个数，
         则搜索下一个上升子序列 */
    if (k < su) { // 搜索完毕后，如果k < su则说明当前搜索的点能接在当前搜索的上升子序列的末尾
        int t = up[k]; // 因为要回溯，所以需要先将更新前的up[k]备份
        up[k] = a[u]; // 将当前搜索的点接在当前上升子序列的末尾（直接更新）
        dfs(u + 1, su, sd); // 继续搜索原序列的下一个点
        up[k] = t; // 回溯(恢复现场)
    }
    else { // 否则，则说明当前搜索的点无法接在当前搜索的上升子序列的末尾，则需要另开一个上升子序列
        up[k] = a[u]; 
        /* 此时因为k = su, 而k最开始是0，所有其实此时已经有了su + 1个上升子序列个数-->
                    此时的up[k]就是新创的一个上升子序列
                再将该点接在该新创的上升子序列的末尾（直接更新）*/
        dfs(u + 1, su + 1, sd); // 继续搜索下一个点，且当前拥有的上升子序列个数+1
    }

// --- 同理得：

    // 情况2：用下降子序列设置系统
    k = 0; // 初始化当前搜索上升子序列序号为0
    while (k < sd && down[k] <= a[u]) k ++ ;
/* 如果当前搜索的点大于等于当前搜索的下降子序列末尾值且当前搜索的序列序号小于当前有的下降子序列的个数，
        则搜索下一个下降子序列 */
    if (k < sd) { // 搜索完毕后，如果k < sd则说明当前搜索的点能接在当前搜索的下降子序列的末尾
        int t = down[k]; // 因为要回溯，所以需要先将更新前的down[k]备份
        down[k] = a[u]; // 将当前搜索的点接在当前下降子序列的末尾（直接更新）
        dfs(u + 1, su, sd); // 继续搜索原序列的下一个点
        down[k] = t; // 回溯(恢复现场)
    }
    else { // 否则，则说明当前搜索的点无法接在当前搜索的上升子序列的末尾，则需要另开一个上升子序列
        down[k] = a[u];
        /* 此时因为k = sd, 而k最开始是0，所有其实此时已经有了sd + 1个上升子序列个数-->
                        此时的down[k]就是新创的一个下降子序列
                再将该点接在该新创的下降子序列的末尾（直接更新）*/
        dfs(u + 1, su, sd + 1); // 继续搜索下一个点，且当前拥有的下降子序列个数+1
    }
}

int main() {
    while (cin >> n, n) { // 处理读入的序列个数，直到输入0为止
        for (int i = 0; i < n; ++ i) cin >> a[i]; 

        ans = n; // 初始化ans为原序列长度
        dfs(0, 0, 0); // 从第一个点(序号为0)，无上升和下降子序列的情况开始暴搜~

        cout << ans << endl; // 输出搜索到的目标最小值ans
    }

    return 0; // 惯例：结束快乐~
}